#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;

//最后一块石头的重量II
//https://leetcode.cn/problems/last-stone-weight-ii/
// class Solution {
// public:
//     int lastStoneWeightII(vector<int>& stones) {
//         //数组[a,b,c,d,e]
//         //第一次选[a-b,c,d,e]
//         //第二次选[a-b,c-d,e]
//         //第三次选[a-b-c+d,e]
//         //第四次选[e-a+b+c-d]
//         //这一题就转换成在数字间添加正负号使得 接近sum/2
//         //假设stones和为sum 在stones数之间添加一些正负号使其 正号数和负号数的差 等于 sum/2
//         //之所以是sum/2是因为我们需要最小重量

//         int n = stones.size();
//         int sum = 0;
//         for(const auto& x:stones) sum += x;
//         int aim = sum/2;

//         //vv[i][k] 表示在前i个数中选择可以凑成k的数
//         //在前0个数中选择可以凑出k是不可能的(石头的最小重量为1)
//         //在前i个数中选择可以凑出0也是不可能的
//         vector<vector<int>> vv(n+1,vector<int>(aim+1));

//         for(int i = 1;i<=n;++i)
//             for(int k = 1;k <= aim;++k)
//             {
//                 vv[i][k] = vv[i-1][k];
//                 if(k>=stones[i-1]) vv[i][k] = max(vv[i][k],vv[i-1][k-stones[i-1]]+stones[i-1]);
//             }

//         //我们需要求最后的差
//         //aim = sum-另一半
//         //另一半 = sum-aim
//         //差 = sum-2*aim
//         return sum - 2*vv[n][aim];
//     }
// };
//优化空间
// class Solution {
// public:
//     int lastStoneWeightII(vector<int>& stones) {
//         int n = stones.size();
//         int sum = 0;
//         for(const auto& x:stones) sum += x;
//         int aim = sum/2;

//         vector<int> vv(aim+1);

//         for(int i = 1;i<=n;++i)
//             for(int k = aim;k>=stones[i-1] && k > 0;--k) //从大向小遍历 如果
//                 vv[k] = max(vv[k],vv[k-stones[i-1]]+stones[i-1]);
        
//         return sum - 2*vv[aim];
//     }
// };




//完全背包
//https://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc?tpId=230&tqId=2032575&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
// const int N = 1010;
// int n = 0,V = 0;
// int v[N],w[N];
// int dp[N][N];
// //(1) dp[i][k] 在前i个物品中选择 在体积V以内可以凑的最大价值
// //(2) dp[i][k] 在前i个物品中选择 凑出体积等于V的最大价值
// int main() {
    
//     while (cin >> n >> V) { 
//         for(int i = 0;i<n;++i)
//             cin>>v[i]>>w[i];

//         //因为一个物品可以选择N次，每到一个物品:
//         //如果不选，则取dp[i-1][k]即可
//         //如果选
//         //选一次i物品是 dp[i][k-v[i]]+w[i]
//         //选两次i物品是 dp[i][k-2*v[i]]+2*w[i]
//         //....
//         //选x次物品是 dp[i][k-x*v[i]]+x*w[i]
//         //则dp[i][k] = max(dp[i][k],dp[i][k-v[i]]+w[i] + dp[i][k-2*v[i]]+2*w[i] + ... + dp[i][k-x*v[i]]+x*w[i])
//         //如此多的状态 我们对其进行数学分析
//         //dp[i][k-v[i]] = max(dp[i][k-v[i]],dp[i][k-2*v[i]]+w[i]+dp[i][k-3*v[i]]+2*w[i]+ ... + dp[i][k-x*v[i]]+(x-1)*w[i])
//         //我们可以发现 dp[i][k-v[i]] 每一项相对于 dp[i][k]来说 少了一个 w[i]
//         //所以 dp[i][k-v[i]]+w[i] 就可以表示后面的dp[i][k-v[i]]+w[i]，dp[i][k-2*v[i]]+2*w[i]...所有状态
//         //dp[i][k] = max(dp[i-1][k],dp[i][k-v[i]]+w[i])

//         //最大价值
//         //因为当物品为0时 想凑出价值是不可能的 所以第一行为0
//         //当物品为i 但需要凑出价值为0时 只需要不选即可 第一列为0
//         for(int i = 1;i<=n;++i)//从第一个物品开始
//             for(int k = 0;k<=V;++k) //从体积为0开始凑
//             {
//                 dp[i][k] = dp[i-1][k];
//                 if(k>=v[i-1]) dp[i][k] = max(dp[i][k],dp[i][k-v[i-1]]+w[i-1]);
//             }
//         cout<<dp[n][V]<<endl;

//         memset(dp,0,sizeof(dp));
//         //填满背包
//         //我们约定 凑不出该体积时 背包中价值为负值
//         //当物品为0个时 我们想凑出价值是不可能的 所以第一行为-0x3f3f3f3f;
//         //当物品为i，凑出0价值只需要不选即可
//         for(int i = 1;i<=V;++i) dp[0][i] = -0x3f3f3f3f;

//         for(int i = 1;i<=n;++i)//从第一个物品开始
//             for(int k = 0;k<=V;++k) //从体积为0开始凑
//             {
//                 dp[i][k] = dp[i-1][k];
//                 if(k>=v[i-1] && dp[i][k-v[i-1]]>=0) dp[i][k] = max(dp[i][k],dp[i][k-v[i-1]]+w[i-1]);
//             }
//         cout<<(dp[n][V]>0?dp[n][V]:0)<<endl;
//     }
//     return 0;
// }
//优化空间
// const int N = 1010;
// int n = 0,V = 0;
// int v[N],w[N];
// int dp[N];
// int main() {
    
//     while (cin >> n >> V) { 
//         for(int i = 0;i<n;++i)
//             cin>>v[i]>>w[i];

           //这里注意需要从左向右填表 因为表达式会用到前面的k-v[i]的状态
//         for(int i = 1;i<=n;++i)//从第一个物品开始
//             for(int k = v[i-1];k<=V;++k) //从体积为0开始凑 k<v[i]不需要进行循环
//                 dp[k] = max(dp[k],dp[k-v[i-1]]+w[i-1]);
            
//         cout<<dp[V]<<endl;

//         memset(dp,0,sizeof(dp));
//         for(int i = 1;i<=V;++i) dp[i] = -0x3f3f3f3f;

//         for(int i = 1;i<=n;++i)//从第一个物品开始
//             for(int k = v[i-1];k<=V;++k) //从体积为v[i]开始凑 k<v[i]不需要进行循环
//                 //因为初始化足够小 所以max不会选择
//                 dp[k] = max(dp[k],dp[k-v[i-1]]+w[i-1]);
            
//         cout<<(dp[V]>0?dp[V]:0)<<endl;
//     }
//     return 0;
// }


//零钱兑换
//https://leetcode.cn/problems/coin-change/
// class Solution {
// public:
//     int coinChange(vector<int>& coins, int amount) {
//         int n = coins.size();

//         //vv[i][k] 表示从前i个硬币中选择可以凑出k值的最小硬币数量
//         vector<vector<int>> vv(n+1,vector<int>(amount+1));

//         const int INF = 0x3f3f3f3f;
//         for(int i = 1;i<=amount;++i) vv[0][i] = INF;

//         for(int i = 1;i<=n;++i)
//             for(int k = 0;k<=amount;++k)
//             {
//                 vv[i][k] = vv[i-1][k];
//                 if(k >= coins[i-1]) vv[i][k] = min(vv[i][k],vv[i][k-coins[i-1]]+1);
//             }

//                 //如果当前的数>=无穷大表示无法选中
//         return vv[n][amount]>=INF?-1:vv[n][amount];
//     }
// };
//优化空间和循环
// class Solution {
// public:
//     int coinChange(vector<int>& coins, int amount) {
//         int n = coins.size();

//         //vv[i][k] 表示从前i个硬币中选择可以凑出k值的最小硬币数量
//         const int INF = 0x3f3f3f3f;
//         vector<int> vv(amount+1,INF);
//         vv[0] = 0;
       
//         for(int i = 1;i<=n;++i)
//             for(int k = coins[i-1];k<=amount;++k)
//                 vv[k] = min(vv[k],vv[k-coins[i-1]]+1);
            
//                 //如果当前的数>=无穷大表示无法选中
//         return vv[amount]>=INF?-1:vv[amount];
//     }
// };